package com.cfw.linkedlist;

import javax.xml.transform.Templates;

/**
 * 模拟单项联表
 * @author Administrator
 *
 */
public class SingleLinkedListDemo {
	
	public static void main(String args[]) {
		//测案例
		
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		
		HeroNode node5 = new HeroNode(5, "节点1","节点1");
		
	
		HeroNode node3 = new HeroNode(3, "节点2","节点2");
		
	
		
		HeroNode node4 = new HeroNode(4, "节点2","节点2");
		HeroNode node1 = new HeroNode(1, "节点2","节点2");
		HeroNode node6 = new HeroNode(6, "节点2","节点2");
		
		
		singleLinkedList.addByOrder(node5);
		singleLinkedList.addByOrder(node4);
		singleLinkedList.addByOrder(node3);
		singleLinkedList.addByOrder(node6);
		singleLinkedList.addByOrder(node1);
//		singleLinkedList.addNode(node1);
		singleLinkedList.addByOrder(node1);
		System.out.println();
		singleLinkedList.list();

		System.out.println("反转链表");

		singleLinkedList.reverseList(singleLinkedList.head.next,singleLinkedList.getLength(),1);

		System.out.println(singleLinkedList.getLength());

		HeroNode newNode = new HeroNode(4,"新节点","新节点");
		//更新
		singleLinkedList.update(newNode);

		System.out.println();
		singleLinkedList.list();

		//删除节点

		singleLinkedList.delete(6);
		System.out.println("删除 6");
		singleLinkedList.list();

		System.out.println(singleLinkedList.getLength());

		singleLinkedList.delete(4);
		System.out.println("删除4");
		singleLinkedList.list();

		singleLinkedList.delete(4);
		System.out.println("删除4");
		System.out.println(singleLinkedList.getLength());

		singleLinkedList.getNode(3);
		singleLinkedList.getNode(2);
		
		
		singleLinkedList.reverseList(singleLinkedList.head);
	}
	
	
	

}
/**
 * 单向链表
 * @author Administrator
 *
 */
class SingleLinkedList{
	
	//头结点数据不能更改
	HeroNode head = new HeroNode(0, "", "");
	
	
	//直接在链表尾部添加,会出现死锁
	public void addNode(HeroNode heroNode) {
		/**
		 *
		 * 不考虑编号顺序，获取到联表最后一个节点，将其next 指向新节点
		 */
		HeroNode tem= head;
		
		while(true) {
			if(tem.next==null) {
				break;
			}
			tem = tem.next;
		}
		tem.next = heroNode;
	}
	
	//根据编号顺序插入
	/**
	 * 找到前一个编号节点，将其next 指向新节点，并把新节点的next指向 原节点的next
	 * @param node
	 */
	public void addByOrder(HeroNode node) {
		
		int no = node.no;
		
		HeroNode tem  = head;//从头节点开始就可以往后添加节点
		
		boolean flag = false;
		
		while(true) {

			if(tem.next ==null) {
				//最后节点
				break;
			}
			if(tem.next.no > node.no) { //不是最后节点，当此节点next 节点的no 大于 插入节点
										//说明位置找对了，就是在tem 节点后面插入即可
				break;
			}else if(tem.next.no == node.no) {
				flag = true;
				break;
			}
			tem = tem.next; //继续遍历
		}
		
		//根据flag 决定是否插入
		if(!flag) {
			//插入链表
			node.next = tem.next;
			tem.next = node;
		}else {
			System.out.println("编号已存在");
		}
		
	}


	//修改节点，根据no 修改

	public void update(HeroNode node) {
		//找到对应的节点

		HeroNode tem = head.next; //头结点不能修改

		Boolean flag = false;


		if(tem == null){
			System.out.println("链表为空");
			return;
		}

		//从头结点后一个节点开始遍历
		while(true){
			if(tem.next==null){
				break;//到了最后的节点
			}
			if(tem.next.no==node.no){
				flag = true;//找到对应节点
				break;
			}
			tem = tem.next;//遍历下一个节点
		}

		if(flag){
			tem.next.name = node.name;
			tem.next.nickName = node.nickName;
		}else{
			System.out.println("节点不存在");
		}
	}


	//删除节点

	public void delete(int no) {

		HeroNode tem = head.next; ////头结点不能删除


		if (tem==null){
			System.out.println("链表为空");
			return;
		}

		Boolean flag = false;

		while(true) {
			if(tem.next==null){
				break;
			}
			if(tem.next.no == no){
				flag = true;
				break;
			}
			tem = tem.next;
		}

		if(flag){
			//因为是根据next判断的，因此，找到节点是tem.next 删除就是将 tem.next 指向 tem.next.next, 也就是直接跳过tem.next
			//原来节点没有被引用后，将会被垃圾回收
			tem.next = tem.next.next;
		}else{
			System.out.println("节点不存在");
		}
	}

	
	//遍历链表
	
	public void list() {
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		
		HeroNode temHeroNode = head.next;
		
		while(true) {
			if(temHeroNode==null) {
				break;
			}
			System.out.println(temHeroNode.toString());
			temHeroNode = temHeroNode.next;
		}
	}


	//获取链表有效个数
	public int getLength() {

		HeroNode tem = head.next;

		int length = 0;

		while (tem!=null){
			length++;
			tem = tem.next;
		}

		return  length;

	}

	//获取第N个节点数据
	public HeroNode getNode(int index) {
		HeroNode node = null;
		int length = getLength();

		if(index>length || index<=0){
			System.out.println("找不到指定节点");
			return node;
		}

		HeroNode tem = head.next;
		Boolean flag = false;
		int count =1;
		while(true){
			if(tem==null){
				break;
			}
			if(count == index){
				flag= true;
				break;
			}
			tem = tem.next;
			count++;
		}

		if(flag){
			System.out.println("找到第"+count+"个节点"+tem.toString());
			return tem;
		}else{
			System.out.println("找不多对应节点数据");
			return null;
		}

	}

	//单链表反转,利用递归的思想
	public void reverseList(HeroNode node,int length,int index){

		System.out.println(index);

		if (index < length){
			reverseList(node.next,length,index+1);
		}

		System.out.println(node.toString());

	}

	//单链表反转，遍历链表，将获取的节点下一个 插入到 原节点之前
	public void reverseList(HeroNode head) {
		SingleLinkedList newList = new SingleLinkedList();

		HeroNode cur = head.next;//当前节点

		HeroNode newHead = new HeroNode(0,"","");
		
		HeroNode next=null;
		HeroNode tem = null;
		
		while(cur!= null){
//			tem = newHead.next ;//保存头部的next，防止丢失 ,可以优化成cur.next = newHead.next;
			next = cur.next;//防止newHead.next.next 修改 cur.next
			cur.next = newHead.next;
			newHead.next = cur;
//			newHead.next.next = tem;//或者写成cur.next=next;		
			cur = next;
			
		}
		newList.head = newHead;
		System.out.println("拆分翻转");
		newList.list();
		
	}

}


/**
 * 节点数据结构
 * @author Administrator
 *
 */
class HeroNode{
	public int no;
	public String nickName;
	public String name;
	public HeroNode next=null;
	
	public HeroNode(int no,String nickName,String name) {
		this.no = no;
		this.nickName = nickName;
		this.name = name;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", nickName=" + nickName + ", name=" + name + "]";
	}
	
}